The task of the assembly of complex physical designs such as device placement in semiconductor chip layouts has been approached in the art in a number of ways. In U.S. Pat. No. 3,654,615, an algorithm is set forth for chip placement and network routing which assigns a first element and then sequentially selects each remaining one until all are assigned, testing each assignment for the incremental effect thereof with respect to the overall array.
The difficulty, however, with such approaches to the design optimization problem that involve measuring improvement attempts over each previous improvement attempt serially is that as the number interrelated discrete elements rises, there will be points where all local rearrangements will operate to make the overall solution worse and the design improvement gets stuck at individual places that may be far from optimum.
In another U.S. Pat. No. 3,621,208 an algorithm that provides trial and error that progresses from the longest to the shortest wire is set forth. This type of technique also occasionally gets stuck at a point that is not acceptable.
While in many instances, such approaches give fairly good results, an approach has not appeared in the art heretofore that will invariably handle the problem of becoming stuck, since the approach to an optimum design rarely flows smoothly from one point to another.